\part{Ejercicio 1}
\section{Enunciado}
Dado un n'umero natural $n$ mayor que 1, encontrar el n'umero primo $p$ que aparece con mayor potencia en la factorizaci'on 
de $n$. En caso de haber m'as de un n'umero primo con  la mayor potencia, encontrar el mayor de ellos.

\section{Desarrollo}
La primera idea para resolver el ejercicio fue obtener los primos menores que el n'umero a factorizar
(en adelante $n$) y luego obtener la potencia con la que cada uno lo divide, qued'andonos con el de mayor
potencia o con el mayor de todos los de m'axima potencia. Sin embargo esta soluci'on era costosa, ya que
requer'ia obtener primeramente todos aquellos primos que sean menores a $n$.
\paragraph{}
Un segundo acercamiento nos permiti'o salvar esta dificultad, de manera que no fue necesario obtener 
los primos menores a $n$ expl'icitamente. El proceso consiste en partir de 2, probar manualmente si 2, 3 y 5 
dividen a $n$ y a partir  de aqu'i ciclar generando n'umeros de la forma $6*k + 1$ o $6*k + 5$ con $k \geq 1$ 
(se demostr'o que todos los n'umeros primos mayores que 5 tienen esta forma en la demostraci'on 1).
\paragraph{}
Cuando hallamos alg'un n'umero primo que divide a $n$, se lo divide y se guarda en $n$ el cociente de dicha 
divisi'on. Mientras el primo siga dividiendo a $n$, vamos guardando la potencia con que lo divide. 
Cuando deja de dividir a $n$, verificamos si es necesario actualizar dicha potencia, y luego construimos 
un nuevo candidato. 
\paragraph{}
Utilizando que si un n'umero es compuesto entonces alg'un primo menor que su ra'iz cuadrada lo divide 
(ver demostraci'on 3) no necesitamos ciclar hasta $n$ sino únicamente hasta su ra'iz cuadrada, o equivalentemente
hasta que el primo actual al cuadrado sea menor que $n$ (recordemos que $n$ se actualiza con cada divisi'on).
\paragraph{}
Usamos la segunda opci'on (elevar el primo al cuadrado en lugar de calcular la ra'iz cuadrada)  ya que en 
el modelo logar'itmico el costo de la ra'iz cuadrada es mayor que el de la multiplicaci'on (ver C'alculo 
de Complejidad). 
\paragraph{}
Una desventaja del m'etodo propuesto es que hace divisiones por n'umeros que no son primos, 
pero igualmente el costo de estas divisiones es menor que el de ver si el n'umero es primo cada vez.Es 
importante notar que si un n'umero no es primo, este no puede dividir a $n$ (ver demostraci'on 2). Si 
no se pudiera asegurar esto, el algoritmo podr'ia fallar.

\newpage
\section{Demostraciones}
\subsection{Teorema 1}
\label{demo1}

\textbf{\underline{Enunciado:}\\}

Sea $p$ $\in$ $\enteros$, primo , $p$ $>$ 5, entonces $\exists$ k $\in$ $\enteros$ $\geq$ 1  tal que $p$ = $6*k+1$ o $p$ = $6*k +5$.\\

\textbf{\underline{Demostraci'on:}\\}

Lo demostraremos por absurdo.\\ 

Supongamos que $\exists$ $p$ $\in$ $\enteros$, primo, tal que $p$ $>$ 5 y $p$ $\not\equiv$ 1  $\mod{6}$ y $p$
$\not\equiv$ 5  $\mod{6}$, luego $p$ = $6*k + j$ con $j$ $\in$ ${0,2,3,4}$ \\

si $j = 0$\\

$6*k$ $\equiv$ 0  $\mod{6}$, absurdo pues $p$ es primo\\

si $j = 2$\\

$6*k + 2$ $\equiv$ 0  $\mod{2}$, absurdo pues $p$ es primo \\

si $j = 3$\\

$6*k + 3$ $\equiv$ 0  $\mod{3}$, nuevamente absurdo\\

si $j = 4$\\

$6*k + 4$ $\equiv$ 0  $\mod{2}$, tambi'en llegamos a un absurdo.\\

Ergo, si $p$ es primo y $p$ $>$ 5, entonces $p$ = $6*k+1$ o $p$ = $6*k +5$.

\subsection{Teorema 2}
\label{demo2}

%\paragraph{Enunciado:}
\textbf{\underline{Enunciado:}\\}

Sea $k$ $\in$ $\enteros$ compuesto, $k$ $>$ 1, y sea $n$ $\entero$ para todo $p$ $\entero$ primo, $p$ $<$ k, $(n:p) = 1$, entonces $n$ $\not\equiv$ 0 $\mod{k}$\\

\textbf{\underline{Demostraci'on:}\\}

Dado que $k$ es compuesto existen $q_1,\ldots,q_j$ con $q_i$ primo tal que $q_1*\ldots*q_j = k$ \\

Supongamos que $n$ $\equiv$ 0 $\mod{k}$,\\

Entonces como los $q_i$ son primos, vale que n $\equiv$ 0 $\mod{q_1}$ $\wedge$ ... $\wedge$ $n \equiv 0 \mod{q_j}$ \\

Pero sabemos que $q_i < k$ y que por lo tanto $(n:q_{i}) = 1$ \\

Llegamos entonces a un absurdo que provino de suponer que  $n \equiv 0 \mod{k}$ \\ 

Luego $n \not\equiv 0 \mod{k}$, que era lo que quer'iamos probar.


\subsection{Teorema 3}
\label{demo3}

\textbf{\underline{Enunciado:}\\}

$k$ $\entero$, $k>1$; $k$ es compuesto $\longleftrightarrow$ $\exists p$ primo tal que $p \leq \sqrt{k}$ y $k \equiv 0 \mod{p}$\\

\textbf{\underline{Demostraci'on:}\\}

Analizamos por separado las dos implicaciones: \\

$\leftarrow)$ trivial \\

$\rightarrow$) Como $k$ es compuesto se puede factorizar como $p_1*...*p_n$\\
supongamos que  $p_i > \sqrt{k} \forall i \in {1...n}$\\

Entonces \\

$k = p_1*...*p_n > (\sqrt{k})^2*T$ , con $T\geq1$\\  

$k = p_1*...*p_n > \sqrt{k}^2*T$ pero $k*T > k$ \\

Absurdo, que provino de suponer que $p_i > \sqrt{k}$ $\forall i \in {1...n}$.\\

\newpage
\section{Pseudoc'odigo}
\input{ejercicio1/seudocodigo/primos.tex}
%En el pseudoc'odigo presentado se utilizan dos funciones auxiliares:
En el pseudoc'odigo presentado se utiliza una funcion auxiliar:
\begin{itemize}
%\item $limite(n)$ es una macro para $\lceil\sqrt{n}\rceil$
\item $generar\_candidato()$ es un procedimiento tipo $factory$ que conserva un estado interno 
y genera candidatos a n'umeros primos como se describi'o en el Teorema 1
\end{itemize}

\newpage
\section{C'alculo de complejidad}
\paragraph{}
En este ejercicio usamos el modelo logar'itmico de complejidad ya que la entrada del problema es 'unicamente un
n'umero entero y el grueso de las operaciones involucradas son 'unicamente sentencias de control de flujo
y operaciones aritm'eticas sobre enteros. En funci'on de esto no ser'ia l'ogico despreciar el aumento del costo
de operar sobre dichos n'umeros a medida que la entrada crece.

\paragraph{}
A partir del pseudoc'odigo se puede identificar r'apidamente el bucle principal donde se realizan la mayor'ia
de las operaciones. Veamos primero el c'odigo fuera del bucle.
\begin{itemize}
\item $generar\_candidato()$ tiene un costo $O(log^2 n)$ ya que para casos grandes solo efect'ua un chequeo de
una variable booleana y una multiplicaci'on de un entero acotado por $n$.
\end{itemize}
El resto de las operaciones realizadas antes y despu'es del bucle tienen una complejidad de a lo sumo $O(log$ $n)$,
y por lo tanto son despreciables respecto del orden predominante que es hasta el momento $O(log^2 n)$ si no tenemos
en cuenta al ciclo principal.

\paragraph{}
Observemos ahora el comportamiento de dicho bucle. Se demostrar'a a continuaci'on que este bucle se ejecuta a lo sumo
$O(\sqrt{n})$ veces, pero por el momento veamos la complejidad del c'odigo contenido en el mismo. Si observamos
l'inea por l'inea el pseudoc'odigo puede verse que el cuerpo del ciclo es una sucesi'on de operaciones aritm'eticas,
donde la m'as costosa es la multiplicaci'on, cuya complejidad es $O(log^2 n)$.

\paragraph{}
Resta entonces demostrar que el ciclo itera a lo sumo $O(\sqrt{n})$ veces. Si analizamos la guarda del ciclo vemos
que se trata de una conjunci'on booleana. Con que cualquiera de las dos formulaciones booleanas sea falsa, el ciclo
termina y el algoritmo se finaliza en tiempo constante. Para que esto ocurra, alcanza con que $n = 1$ o $primoActual^2
> limite$ o equivalentemente $primoActual > \sqrt{limite}$. Represento por $nombre_i$ el valor de la variable $nombre$ 
en la iteraci'on $i$. 

\paragraph{}
Al entrar al ciclo hay dos casos posibles: o bien $primoActual$ $|$ $n$, o no lo hace. Llamemos a estas dos
posibilidades caso 1 y caso 2 respectivamente, y analicemos por separado.
\begin{itemize}
\item Caso 1: $primoActual$ $|$ $n$ \\
En este caso se divide a $n$ por $primoActual$ mientras sea posible. Como $primoActual \geq 2$, resulta
sencillamente que la cantidad de veces que puede ejecutarse este bloque es $O(log_2 n)$. Necesariamente
despu'es de esa cantidad de iteraciones tendremos $n = 1$ y el ciclo termina.
\item Caso 2: $primoActual \nmid n$\\
En este otro caso se cumple que $\forall n > N$, $primoActual_{i+1} \geq primoActual_i + 1$. Esto se deduce
por construcci'on del procedimiento $generar\_candidatos()$ que produce una sucesi'on de la forma: \\

\centerline{2, 3, 5, 6 * 1 + 1, 6 * 1 + 5, 6 * 2 + 1, 6 * 2 + 5, 6 * 3 + 1, 6 * 3 + 5 ...} 

Si adem'as vemos que en este caso $primoActual_{i+1}$ es el t'ermino de la sucesi'on que est'a 
inmediatamente a continuaci'on de $primoActual_i$. Por consiguiente $primoActual$ crece
de forma tal que supera el valor de $\sqrt{limite}$ en $O(\sqrt{limite})$ iteraciones (puesto
que $primoActual > 0$ en todo momento, $|primoActual - \sqrt{limite}|$ $< \sqrt{limite}$).
Adem'as resulta claro que $limite \leq n$ ya que su valor inicial es $n$ y luego decrece
progresivamente.
\end{itemize}

\paragraph{}
Finalmente vemos que el caso 1 resulta en a lo sumo $O(log_2 n)$ iteraciones, mientras que
el caso 2 resulta en $O(\sqrt{n})$. Por lo tanto la totalidad de iteraciones es:\\
\\
\centerline{$O(log_2 n + \sqrt{n}) = O(\sqrt{n})$}
\paragraph{}
Y el orden de complejidad del ciclo teniendo en cuenta el costo de cada iteraci'on es por lo tanto:\\
\\
\centerline{$O(log^2 (n) \sqrt{n})$}
\paragraph{}
Siendo $n$ el valor del entero que el algoritmo toma como par'ametro. Por otra parte sabemos que 
el tama\~{n}o en memoria de un entero arbitrario $n$ es $t = log_2 n$, por lo tanto, el tama\~{n}o de la entrada no es n, sino t:\\
\\
\centerline{$2^t = n \Rightarrow \sqrt{n}$ $log^2 n = 2^{t/2}$ $t^2$}
\paragraph{}
Finalmente pudimos demostrar que $T(t) \in O(2^{t/2} $ $t^2)$.
\paragraph{}
Cuando un n'umero es primo, ocurre que el ciclo itera exactamente $\sqrt{n}$ veces, mientras que si el n'umero es 
compuesto la cantidad de iteraciones es menor, ya que si $n = p_{1}^{k_{1}}*m$ donde $p_1$ es primo y es el menor 
primo que divide a $n$, tenemos que el ciclo va a iterar aproximadamente $p_1$ veces hasta hallar a $p_1$, luego 
$k_1$ veces y por ende como m'aximo $\sqrt{m}-p_1$ veces.
\paragraph{}
En particular si el n'umero $n$ es de la forma $p^k$ con $p$ primo, el ciclo itera hasta $p$ y luego itera $k$ veces,
y $k=log_p n$ por lo que la cantidad de iteraciones va a ser logar'itmica. Si lo pensamos en funci'on del 
tama\~{n}o de la entrada, si $n$ es primo se producen $O(2^{t/2})$ iteraciones, mientras que si el n'umero es 
una potencia de un primo, el n'umero de iteraciones es $O(t)$.

\section{An'alisis Experimental}
\subsection{Experiencias realizadas}
\paragraph{}
Para el an'alisis del algoritmo decidimos medir tanto operaciones como tiempo. 
\paragraph{}
Primero medimos dichas variables para los n'umeros entre 2 y 100000 para observar un patr'on de comportamiento. 
A partir de esta experiencia, decidimos realizar otras dos, donde separamos n'umeros primos en una de ellas, y en 
la otra tomamos las potencias de un n'umero primo (en particular de 7). Esto lo hicimos por considerar que el peor caso
del algoritmo es precisamente cuando el n'umero es primo, mientras que el mejor caso es cuando el n'umero es 
potencia de un primo. 
\paragraph{}
Por otro lado realizamos experiencias similares pero teniendo en cuenta ya no el n'umero, sino la cantidad de bits 
de su representaci'on binaria, es decir teniendo en cuenta el tama\~{n}o de la entrada. Para estas experiencias 
tomamos distintos n'umeros pero medimos la cantidad de operaciones y el tiempo en funci'on de $\lfloor log_2(n) \rfloor + 1$.
\paragraph{}
Para medir los tiempos se utiliz'o una clase basada en $QueryPerformanceCounter$ de Win32. Para contar operaciones, 
el procedimiento se bas'o en declarar una variable global e ir increment'andola en base a las operaciones que se 
realizaban l'inea a l'inea. Este procedimiento se aplic'o en los tres ejercicios.

\subsection{Gr'aficos}
\subsubsection{Gr'aficos en funcion de n}

\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{../../codigo/ejercicio1/benchmark/graficos/todos_los_numeros/graficosTodos.png}
\caption{Cantidad de operaciones en funci'on de $n$}
\label{Ej1fig1}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{../../codigo/ejercicio1/benchmark/graficos/primos/graficoPrimos.png}
\caption{Cantidad de operaciones en funci'on del $n$ para $n$ primo}
\label{Ej1fig2}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{../../codigo/ejercicio1/benchmark/graficos/potencias_de_7/graficoPotenciasDe7.png}
\caption{Cantidad de operaciones en funci'on de $n$ para $n$ de la forma $7^k$}
\label{Ej1fig3}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{../../codigo/ejercicio1/benchmark_de_tiempo/graficos/todos_los_numeros/todosLosNumerosPuntosTiempo.png}
\caption{Tiempo en funci'on de $n$}
\label{Ej1fig4}
\end{figure}

\subsubsection{Gr'aficos en funcion del tama\~{n}o de la entrada}
\begin{figure}[H]
\centering
\includegraphics[scale=0.6]{../../codigo/ejercicio1/benchmark/graficos/tamanio_Entrada_T/operacionesEntrada.png}
\caption{Cantidad de operaciones en funci'on del tama\~{n}o de la entrada}
\label{Ej1fig5}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.65]{../../codigo/ejercicio1/benchmark_de_tiempo/graficos/tamanio_Entrada_T/Tiempo_en_funcion_bits.png}
\caption{Tiempo en funci'on del tama\~{n}o de la entrada}
\label{Ej1fig6}
\end{figure}
\newpage
\section{Discusi'on}
\paragraph{}
En los gr'aficos pudimos observar lo que el an'alisis te'orico nos anunci'o.
\paragraph{}
En la figura 1, se ve claramente como existen diversos patrones de comportamiento. As'i el techo es un funci'on del tipo ra'iz 
cuadrada, mientras que debajo se encuentran otras funciones de orden logar'itmico. Esta situaci'on se ve mas claro en los 
gr'aficos donde s'olo est'an los n'umeros primos. En ambos casos pudimos, mediante cuadrados m'inimos, 
encontrar una funci'on que se asemeje al comportamiento de las muestras, lo cual refuerza nuestra idea de mejor y peor caso.
\paragraph{}
El gr'afico en funci'on del tiempo muestra un comportamiento muy similar al gr'afico de cantidad de operaciones, pero presenta 
$outliers$ que se pueden explicar por el hecho de que tomar tiempos esta sujeto a un error de medici'on producto del uso del sistema
de pruebas por parte de otros procesos.
\paragraph{}
A la hora de analizar los gr'aficos en funci'on del tama\~{n}o de la entrada esperamos ver g'raficos con forma exponencial 
y fue exactamente eso lo que obtuvimos. En el caso de cantidad de operaciones, se mantuvo lo observado en los otros gr'aficos, 
es decir que en general los primos requieren m'as operaciones que el resto de los n'umeros, mientras que las potencias de 7 
requieren muchas menos.
\paragraph{}
Finalmente la figura 6 mantiene la tendencia, y nuevamente presenta $outliers$ propios de los factores externos que intervienen 
en la medici'on de tiempos.
\paragraph{}
A modo de conclusi'on podemos afirmar que la experimentaci'on emp'irica valid'o nuestros resultados te'oricos.
